#include "trees.h"
#include "simple-path.h"
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <sstream>

using namespace std;

/////////////////////////////////////////////////////////////////////////////////////////////////
//
//				S I M P L E   P A T H   T R E E     I M P L E M E N T A T I O N
//
/////////////////////////////////////////////////////////////////////////////////////////////////
template <class V, class E>
Trees::SimplePathTree<V,E>::SimplePathTree(const V& value, DotPrinter* forest) 
	: DynamicPathTree<V,E>(value), m_after(NULL), m_before(NULL), m_forest(forest)
{
	m_path = new SimplePath<V,E>(this);
}

template <class V, class E>
Trees::SimplePathTree<V,E>::~SimplePathTree()
{
#ifdef TREE_DEBUG
	cerr << "~SimplePathTree(): " << this->Value() << endl;
#endif	
	if ( !Before() )
	{
		delete m_path;
	}
}
		
template <class V, class E>
const E Trees::SimplePathTree<V,E>::MinEdge() const
{
	return 25;
}

template <class V, class E>
const E Trees::SimplePathTree<V,E>::MaxEdge() const
{
	return 25;
}

template <class V, class E>
Trees::Path<V,E>* Trees::SimplePathTree<V,E>::GetPath() const
{
#ifdef TREE_DEBUG
	cerr << "GetPath(" << this->Value() << ") >>>" << endl;
#endif
	SimplePathTree<V,E>* t = const_cast<SimplePathTree<V,E> *>(this);
	DynamicPathTree<V,E>* next;
	while ( next = const_cast<DynamicPathTree<V,E> *>(t->Before()) )
	{
		t = dynamic_cast<SimplePathTree<V,E> *>(next);
	}
#ifdef TREE_DEBUG	
	cerr << "GetPath(" << this->Value() << ") <<< return Path_" << t->m_path->m_id << endl;
#endif
	return t->m_path;
}

template <class V, class E>
Trees::DynamicPathTree<V,E>* Trees::SimplePathTree<V,E>::Before() const
{
	return m_before;
}

template <class V, class E>
Trees::DynamicPathTree<V,E>* Trees::SimplePathTree<V,E>::After() const
{
	return m_after;
}

template <class V, class E>
const E Trees::SimplePathTree<V,E>::PCost() const
{
	if ( !m_after )
	{
		throw IllegalTreeOperationException();
	}
	return m_cost;
}

template <class V, class E>
void Trees::SimplePathTree<V,E>::Split(Path<V,E>** p, Path<V,E>** q, E* x, E* y, const string& logPrefix)
{
#ifdef TREE_DEBUG
	std::ostringstream stringStream;
	stringStream << logPrefix << " / Split(" << this->Value() << ")";
	string logLabel = stringStream.str();
	cerr << logLabel << " >>> " << endl;
	m_forest->printDot(cout, ("BEFORE" + logLabel).c_str());
#endif

	SimplePath<V,E>* path = dynamic_cast<SimplePath<V,E> *>( GetPath() );
	SimplePathTree<V,E>* head = dynamic_cast<SimplePathTree<V,E>* >(path->Head()); 
	SimplePathTree<V,E>* tail = dynamic_cast<SimplePathTree<V,E>* >(path->Tail());
	
	SimplePathTree<V,E>* v = this;
	
	if ( v->m_before )
	{
		head->m_path = new SimplePath<V,E>(head, v->m_before);;
		*p = head->m_path;
		*x = v->m_before->m_cost;
		v->m_before->m_after = NULL;
		v->m_before->m_dParent = NULL;
		v->m_before = NULL;
	}
	else 
	{
		*p = NULL;
	}
	if ( v->m_after )
	{
		v->m_after->m_path = new SimplePath<V,E>(v->m_after, dynamic_cast<SimplePathTree<V,E>*>(path->Tail()) );
		*q = v->m_after->m_path;
		*y = v->m_cost;
		v->m_after->m_before = NULL;
		v->m_after = NULL;
		v->m_dParent = NULL;
	}
	else
	{
		*q = NULL;
	}
	v->m_path = path;
	path->m_head = v;
	path->m_tail = v;

#ifdef TREE_DEBUG
	m_forest->printDot(cout, logLabel.c_str());
	cerr << "Split(" << this->Value() << ") <<< " << endl;
#endif	
}

template <class V, class E>
void Trees::SimplePathTree<V,E>::Link(DynamicTree<V,E>* otherRoot, const E& x)
{
#ifdef TREE_DEBUG
	cerr << "Link(" << this->Value() << ", " << otherRoot->Value() << ") >>> " << endl;
#endif
	DynamicPathTree<V,E>::Link(otherRoot, x);
#ifdef TREE_DEBUG	
	m_forest->printDot(cout, "Link(%d, %d, %d)", this->Value(), otherRoot->Value(), x);
	cerr << "Link(" << this->Value() << ", " << otherRoot->Value() << ") >>> " << endl;
#endif
}

template <class V, class E>
Trees::Path<V,E>* Trees::SimplePathTree<V,E>::Expose(const string& logPrefix) const
{
	std::ostringstream stringStream;
	stringStream << logPrefix << " / Expose(" << this->Value() << ")";
	string logLabel = stringStream.str();
#ifdef TREE_DEBUG
	cerr << logLabel << " >>> " << endl;
#endif
	Path<V,E>* p;
	Path<V,E>* q;
	Path<V,E>* r;
	E x, y;
	
	SimplePathTree<V,E>* inst = const_cast<SimplePathTree<V,E> *>(this);
	inst->Split(&q, &r, &x, &y, logLabel);
	if ( q )
	{
		DynamicPathTree<V,E>* qTail = dynamic_cast<DynamicPathTree<V,E> *>( q->Tail() );
		qTail->m_dParent = inst;
		qTail->m_dCost = x;
	}
	
	p = GetPath();
	if ( r )
	{
		p->Concatenate(r, y);
	}
	while ( p->Tail()->DParent() )
	{
		p = p->Splice();
	}

#ifdef TREE_DEBUG
	m_forest->printDot(cout, logLabel.c_str());
	cerr << logLabel << ") <<< " << endl;
#endif	
	return p;
}

/////////////////////////////////////////////////////////////////////////////////////////////////
//
//				S I M P L E   P A T H   I M P L E M E N T A T I O N
//
/////////////////////////////////////////////////////////////////////////////////////////////////

int simplePathInstCount = 0;

template <class V, class E>
Trees::SimplePath<V,E>::SimplePath(SimplePathTree<V,E>* head) : m_head(head), m_tail(head)
{
	m_id = ++simplePathInstCount;
}

template <class V, class E>
Trees::SimplePath<V,E>::SimplePath(SimplePathTree<V,E>* head, SimplePathTree<V,E>* tail) 
		: m_head(head), m_tail(tail)
{
	m_id = ++simplePathInstCount;
}

template <class V, class E>
Trees::SimplePath<V,E>::~SimplePath()
{
#ifdef TREE_DEBUG
	cerr << "~SimplePath(): this=" << this << " m_head=" << m_head->Value() << endl;
#endif
}
		
template <class V, class E>
Trees::DynamicPathTree<V,E>* Trees::SimplePath<V,E>::Head() const
{
	return m_head;
}

template <class V, class E>
Trees::DynamicPathTree<V,E>* Trees::SimplePath<V,E>::Tail() const
{
	return m_tail;
}

template <class V, class E>
Trees::DynamicPathTree<V,E>* Trees::SimplePath<V,E>::PMinCost() const
{
#ifdef TREE_DEBUG
	cerr << "PMinCost(Path_" << m_id << ") >>>" << endl;
#endif	
	E min = max_value<E>();
	SimplePathTree<V,E>* minNode = NULL;
	SimplePathTree<V,E>* t = m_head;
	SimplePathTree<V,E>* next;
	
	while ( next = dynamic_cast<SimplePathTree<V,E>*>(t->After()) )
	{
		if ( t->m_cost <= min )
		{
			min = t->m_cost;
			minNode = t;
		}
		t = next;
	}
#ifdef TREE_DEBUG
	cerr << "PMinCost(Path_" << m_id << ") <<< return " << minNode->Value() << endl;
#endif
	return minNode;
}

template <class V, class E>
void Trees::SimplePath<V,E>::PUpdate(const E& x)
{
	SimplePathTree<V,E>* t = m_head;
	SimplePathTree<V,E>* next;
	while ( next = dynamic_cast<SimplePathTree<V,E>*>(t->After()) )
	{
		t->m_cost = sum(t->m_cost, x);
		t = next;
	}
}

template <class V, class E>
void Trees::SimplePath<V,E>::Reverse()
{
#ifdef TREE_DEBUG
	m_head->m_forest->printDot(cout, "BEFORE Reverse(Path_%d)", m_id);
#endif
	SimplePathTree<V,E>* tmp;
	E previousCost;
	
	SimplePathTree<V,E>* t = m_head;
	
	while ( t )
	{
		E thisCost = t->m_cost;
		SimplePathTree<V,E>* next = t->m_after;

		if ( t->m_before )
		{
			t->m_cost = previousCost;
		}

		tmp = t->m_before;
		t->m_before = t->m_after;
		t->m_after = tmp;
		previousCost = thisCost;
	
		t = next;
	}
	tmp = m_tail;
	m_tail = m_head ;
	m_head = tmp;
	
	m_tail->m_path = NULL;
	m_head->m_path = this;

#ifdef TREE_DEBUG
	m_head->m_forest->printDot(cout, "Reverse(Path_%d)", m_id);
#endif
}

template <class V, class E>
Trees::Path<V,E>* Trees::SimplePath<V,E>::Concatenate(Path<V,E>* p_tail, const E& x)
{
	SimplePath<V,E>* tail = dynamic_cast<SimplePath<V,E> *>(p_tail);
	int tailId = tail->m_id;
	
#ifdef TREE_DEBUG
	cerr << "Concatenate(Path_" << m_id << ", Path_" <<  tailId << ") >>>" << endl;
#endif	
	
	m_tail->m_after = tail->m_head;
	m_tail->m_dParent = NULL;
	tail->m_head->m_before = m_tail;
	m_tail->m_cost = x;
	m_tail = tail->m_tail;
	
	SimplePathTree<V,E>* tailHead = tail->m_head;
	
	tailHead->m_path = NULL;
	
	delete p_tail;

#ifdef TREE_DEBUG
	m_head->m_forest->printDot(cout, "Concatenate(Path_%d, Path_%d, %d)", m_id, tailId, x);
	cerr << "Concatenate(Path_" << m_id << ", Path_" <<  tailId << ") <<<" << endl;
#endif
	
	return this;
}

template <class V, class E>
Trees::Path<V,E>* Trees::SimplePath<V,E>::Splice()
{
#ifdef TREE_DEBUG
	cerr << "Splice(Path_" << m_id << ") >>>" << endl;
	m_head->m_forest->printDot(cout, "BEFORE: Splice(Path_%d)", m_id);
#endif
	SimplePathTree<V,E>* v = dynamic_cast<SimplePathTree<V,E> *>( Tail()->DParent() );
	if ( !v )
	{
		throw IllegalTreeOperationException();
	}
	
	Path<V,E>* q = NULL;
	Path<V,E>* r = NULL;
	E x, y;
	
	v->Split(&q, &r, &x, &y);
	if ( q )
	{
		q->Tail()->m_dParent = v;
		q->Tail()->m_dCost = x;
	}

	Path<V,E>* p = Concatenate(v->GetPath(), Tail()->DCost());

	if ( r )
	{
		p->Concatenate(r, y);
	}

#ifdef TREE_DEBUG	
	m_head->m_forest->printDot(cout, "Splice(Path_%d)", m_id);
	cerr << "Splice(Path_" << m_id << ") <<<" << endl;
#endif
	return p;
	
}

template class Trees::SimplePathTree<int,int>;

template class Trees::SimplePathTree<int, Trees::EdgeInfo<int> >;
